package acm.天梯赛4;

import java.util.Scanner;

public class E {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int count = sc.nextInt();
        while (count-- > 0) {
            System.out.println(fun(sc.nextInt(),sc.nextInt()));
        }
    }
    public static int fun(int n,int k){
        int curr=n;
        int count=0;
        while (curr>k){
            curr=curr-curr/k;
            count++;
        }
//        1737
//        2147483647
//        2141224492
//        6259155*1737
//        int ss=625915500000;
        for (int i = n; i >= k; i--) {
            int m=i;
            boolean isOk =true;
            for (int j = 0; j < count; j++) {
                if (m%k==0){
                    isOk=false;
                    break;
                }
                m=m-m/k;
            }
            if (isOk){
                return i;
            }
        }
        return 0;
    }
}
